package Tree._117_PopulatingNextRightPointersinEachNodeII;

import java.util.ArrayList;
import java.util.List;

public class _117_PopulatingNextRightPointersinEachNodeII {

    public void connect_1(TreeLinkNode root) {
        if(root==null) return;
        List<TreeLinkNode> nodes = new ArrayList<>();
        nodes.add(root);
        while (!nodes.isEmpty()) {
            List<TreeLinkNode> tmp = new ArrayList<>();
            for (int i=0;i<nodes.size();i++) {
                TreeLinkNode node = nodes.get(i);
                if (i != nodes.size() - 1) {
                    node.next = nodes.get(i + 1);
                }else{
                    node.next = null;
                }
                if (node.left != null) {
                    tmp.add(node.left);
                }
                if (node.right != null) {
                    tmp.add(node.right);
                }
            }
            nodes = tmp;
        }
    }

    //solution 2: iterate every level,use prev node.
    public void connect(TreeLinkNode root) {
        TreeLinkNode dummyHead = new TreeLinkNode();
        TreeLinkNode prev = dummyHead;
        while (root != null) {
            if (root.left != null) {
                prev.next = root.left;
                prev = prev.next;
            }
            if (root.right != null) {
                prev.next = root.right;
                prev = prev.next;
            }
            root = root.next;
            if (root == null) {
                root = dummyHead.next;
                prev = dummyHead;
                dummyHead.next = null;
            }
        }
    }
}
